package com.liuhm.bfs.utils;

import com.liuhm.bfs.*;
import javafx.scene.Parent;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 画布测试
 *
 * @author liuhaomin
 * @date 2020/12/29
 */
public class Dag3Utils {
    public static void main(String[] args) {
        Dag3 dag = getDag3();

        long start = System.currentTimeMillis();
        // 单线路
//            doTasks(DFS(dag.getChildrenRoot()));
//        doTasks(BFS(dag.getChildrenRoot()));
        // 分层并行
        Map<String, List<VertexVersion>> stringListMap = BFSNew(dag.getChildrenRoot());
        stringListMap.forEach((key,value)->{
            doTasksNew(value);
        });
        long end = System.currentTimeMillis();
        System.out.println(end-start);

    }
    public static Dag3 getDag3(){
        Dag3 dag = new Dag3();
      /*  dag.addEdge("a","1","c","2");
        dag.addEdge("b","1","c","2");
        dag.addEdge("c","2","d","3");
        dag.addEdge("f","5","e","4");
        dag.addEdge("d","3","e","4");
        dag.addEdge("e","4","g","6");
        dag.addEdge("h","3","j","8");
        dag.addEdge("i","7","j","8");
        dag.addEdge("j","8","k","9");
      */
        dag.addEdge("T1","1",false,"S1","3",true);
        dag.addEdge("T2","2",false,"S1","3",true);
        dag.addEdge("T2","2",false,"S4","10",true);
        dag.addEdge("S4","10",true,"T7","11",false);
        dag.addEdge("S1","3",true,"T3","4",false);
        dag.addEdge("T3","4",false,"S2","5",true);
        dag.addEdge("S2","5",true,"T4","6",false);
        dag.addEdge("T4","6",false,"S3","8",true);
        dag.addEdge("T5","7",false,"S3","8",true);
        dag.addEdge("S3","8",true,"T6","9",false);
        dag.addEdge("T6","9",false,"S5","12",true);
        dag.addEdge("T7","11",false,"S5","12",true);
        dag.addEdge("S5","12",true,"T8","13",false);
        dag.addEdge("T9","9",false,"S6","14",true);
        dag.addEdge("S6","14",true,"T11","15",false);
        dag.addEdge("T11","15",false,"S7","17",true);
        dag.addEdge("T10","16",false,"S7","17",true);
        dag.addEdge("S7","17",true,"T12","18",false);
        return dag;
    }

    /**
     * 深度遍历
     * @param  root
     * @return
     */
    public static List<VertexVersion> DFS(List<VertexVersion> root){
        List<VertexVersion> all = new ArrayList<>();
        Stack<VertexVersion> stack =new Stack<VertexVersion>();
        for (VertexVersion vertex : root) {
            stack.add(vertex);
        }
        Map<String, VertexVersion> visited = new HashMap<>();
        while(stack.size()>0){
            int size = stack.size();
            for (int i = 0; i < size; i++) {
                //pop vertex
                VertexVersion currVert = stack.pop();
                if(visited.get(currVert.getKey())!=null){
                    continue;
                }
                if( currVert.getParented()!=null && currVert.getParented() ){
                    boolean flag = false;
                    for (VertexVersion child : currVert.getChildren()) {
                        if( visited.get(child.getKey()) == null ){
                            flag = true;
                            break;
                        }
                    }
                    if(flag){
                        continue;
                    }
                }
                visited.put(currVert.getKey(),currVert);
                all.add(currVert);
                for (VertexVersion parent : currVert.getParents()) {
                    if(visited.get(parent.getKey()) == null){
                        stack.add(parent);
                    }
                }
            }
        }
        List<VertexVersion> result = new ArrayList<>();
        for (int i = all.size() - 1; i >= 0; i--) {
            result.add(all.get(i));
        }
        return result;
    }
    /**
     * 广度遍历
     * @param  root
     * @return
     */
    public static List<VertexVersion> BFS(List<VertexVersion> root){
        List<VertexVersion> all = new ArrayList<>();
        Queue<VertexVersion> queue = new LinkedList<VertexVersion>();
        for (VertexVersion vertex : root) {
            queue.add(vertex);
        }
        Map<String, VertexVersion> visited = new HashMap<>();
        while(queue.size()>0){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                //pop vertex
                VertexVersion currVert = queue.poll();
                if(visited.get(currVert.getKey())!=null){
                    continue;
                }
                if( currVert.getParented()!=null && currVert.getParented() ){
                    boolean flag = false;
                    for (VertexVersion child : currVert.getChildren()) {
                        if( visited.get(child.getKey()) == null ){
                            flag = true;
                            break;
                        }
                    }
                    if(flag){
                        continue;
                    }
                }
                visited.put(currVert.getKey(),currVert);
                all.add(currVert);
                for (VertexVersion parent : currVert.getParents()) {
                    if(visited.get(parent.getKey()) == null){
                        queue.add(parent);
                    }
                }
            }
        }
        List<VertexVersion> result = new ArrayList<>();
        for (int i = all.size() - 1; i >= 0; i--) {
            result.add(all.get(i));
        }
        return result;
    }


    public static void doTasks(List<VertexVersion> vertexDTOList){
        for (VertexVersion vertexDTO : vertexDTOList) {
            if(vertexDTO.getCalc()){
                try {
                    Thread.sleep(1000);
                    System.out.println("key:"+vertexDTO.getKey()+",value:"+vertexDTO.getValue());
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
        System.out.println("-------------------------doTasks end-------------------------");

    }

    /**
     * 广度遍历
     * @param  root
     * @return
     */
    public static Map<String, List<VertexVersion>> BFSNew(List<VertexVersion> root){
        Map<String, List<VertexVersion>> all = new HashMap<>();
        Queue<VertexVersion> queue = new LinkedList<VertexVersion>();
        for (VertexVersion vertex : root) {
            queue.add(vertex);
        }
        Map<String, VertexVersion> visited = new HashMap<>();
        int num = 0;
        while(queue.size()>0){
            List<VertexVersion> tmp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                //pop vertex
                VertexVersion currVert = queue.poll();
                if(visited.get(currVert.getKey())!=null){
                    continue;
                }
                if( currVert.getParented()!=null && currVert.getParented() ){
                    boolean flag = false;
                    for (VertexVersion child : currVert.getChildren()) {
                        if( visited.get(child.getKey()) == null ){
                            flag = true;
                            break;
                        }
                    }
                    if(flag){
                        continue;
                    }
                }
                visited.put(currVert.getKey(),currVert);
                tmp.add(currVert);
                for (VertexVersion parent : currVert.getParents()) {
                    if(visited.get(parent.getKey()) == null){
                        queue.add(parent);
                    }
                }
            }
            all.put(getKey(num),tmp);
            num++;
        }
        Map<String, List<VertexVersion>>  result = new HashMap<>();
        int size = all.size();
        int i = 0 ;
        for (List<VertexVersion> dataList:all.values()){
            i++;
            result.put(getKey(size-i),dataList);
        }
        return result;
    }
    /**
     * 获取 a,b,c,d,e,f,g的排序
     * @param   index
     * @return
     */
    public static String getKey(int index){
        String colCode = "";
        char key='a';
        int loop = index / 26;
        if(loop>0){
            colCode += getKey(loop-1);
        }
        key = (char) (key+index%26);
        colCode += key;
        return colCode;
    }
    // 并发执行
    public static void doTasksNew(List<VertexVersion> vertexDTOList){
        Vector<Thread> threadVector = new Vector<Thread>();
        for (VertexVersion vertexDTO : vertexDTOList) {
            if(vertexDTO.getCalc()){
                Thread t = new Thread(() -> {
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println("key:"+vertexDTO.getKey()+",value:"+vertexDTO.getValue());
                });
                threadVector.add(t);
                t.start();
            }
        }
        System.out.println("--------------------------------");
        for (Thread thread : threadVector) {
            try {
                thread.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}
